#include <iostream>
#include "euler/pell.hpp"
#include "euler.h"

BEGIN_PROBLEM(140, solve_problem_140)
	PROBLEM_TITLE("Polynomial series with recursive coefficients")
	PROBLEM_ANSWER("5673835352990")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("n")
	PROBLEM_SPACE_COMPLEXITY("1")
	PROBLEM_KEYWORDS("recurrence,Pell")
END_PROBLEM()

static void solve_problem_140()
{
	bool verbose = false;
	int N = 30;

	// x^2 - 5*y^2 = 44, (x,y) = (7,1), (8,2), (13,5), (17,7), (32,14), (43,19)
	// x^2 - 5*y^2 = 1,  (x,y) = (9,4)
	typedef euler::pell_solution_iterator<long long,int> Iter;
	Iter xy1(5, 9, 4, 7, 1);
	Iter xy2(5, 9, 4, 8, 2);
	Iter xy3(5, 9, 4, 13, 5);
	Iter xy4(5, 9, 4, 17, 7);
	Iter xy5(5, 9, 4, 32, 14);
	Iter xy6(5, 9, 4, 43, 19);
	Iter xy[] = { xy1, xy2, xy3, xy4, xy5, xy6 };
	long long sum = 0;
	int i = 0;
	for (int n = 0; n < N; ++xy[i], i=(i+1)%(sizeof(xy)/sizeof(xy[0])))
	{
		long long x = xy[i]->first;
		if (x % 5 == 2 && x > 7)
		{
			if (verbose)
			{
				std::cout << (n+1) << "th golden nugget (from " << (i+1) << ") is "
					<< (x-7)/5 << std::endl;
			}
			sum += (x-7)/5;
			++n;
		}
	}
	std::cout << sum << std::endl;
}
